package lab2;

import java.util.Iterator;

public class MyHashMap<K, V> implements MyMap<K, V> {

	static class SimpleEntry<K, V> implements MyMap.Entry<K, V> {

		final K key;
		V value;
		final int hash;
        SimpleEntry<K, V> next;

        SimpleEntry() {
        	this.key = null;
        	this.value = null;
        	this.hash = -1;
        	next = null;
        }

        SimpleEntry(final K key, final V value) {
        	this.key = key;
        	this.value = value;
        	this.hash = hash(key.hashCode());
        	next = null;
        }

        SimpleEntry(final K key, final V value, final int hash) {
        	this.key = key;
        	this.value = value;
        	this.hash = hash;
        	next = null;
        }
        
        SimpleEntry(final K key, final V value, final int hash, final Entry<K, V> next) {
        	this.key = key;
        	this.value = value;
        	this.hash = hash;
        	this.next = (SimpleEntry<K, V>) next;
        }

        public boolean equals(final Object o) {
			if (!(o instanceof SimpleEntry<?, ?>)) {
				return false;
			}

			return (key == null ? ((SimpleEntry<?, ?>) o).getKey() == null
					: key.equals(((SimpleEntry<?, ?>) o).getKey())) &&
				     (value == null ? ((SimpleEntry<?, ?>) o).getValue() == null
				     : value.equals(((SimpleEntry<?, ?>) o).getValue()));
		}

		public int hashCode() {
			return (key == null ? 0 : key.hashCode()) ^
					(value == null ? 0 : value.hashCode());
		}

		public K getKey() {
			K res = key;
			return res;
		}

		public V getValue() {
			V res = value;
			return res;
		}


		public SimpleEntry<K, V> getNext() {
			return next;
		}

		public void setNext(final Entry<K, V> e) {
			next = (SimpleEntry<K, V>) e;
		}

		public int getHash() {
			return hash;
		}

		public V setValue(final V value) {
			V res = null;

			if (this.value != null) {
				res = this.value;
			}

			this.value = value;

			return res;
		}

	}

	/**
	 * The maximum capacity, used if a higher value is implicitly specified
	 * by either of the constructors with arguments.
	 * MUST be a power of two <= 1<<30.
	 */
	static final int MAXIMUM_CAPACITY = 1 << 30;

	/**
	 * The default initial capacity - MUST be a power of two.
	 */
	static final int DEFAULT_INITIAL_CAPACITY = 16;

	/**
	 * The load factor used when none specified in constructor.
	 */
	static final float DEFAULT_LOAD_FACTOR = 0.75f;

	int MY_INITIAL_CAPACITY;

	float MY_LOAD_FACTOR;

	int capacity;

	int size;

	transient Entry<K, V>[] table;

	public MyHashMap() {
		MY_INITIAL_CAPACITY = DEFAULT_INITIAL_CAPACITY;
		capacity = DEFAULT_INITIAL_CAPACITY;
		MY_LOAD_FACTOR = DEFAULT_LOAD_FACTOR;
		table = new Entry[capacity];
		size = 0;
	}

	public MyHashMap(final int initialCapacity) {
		if (initialCapacity < 0) {
			throw new IllegalArgumentException();
		}

		MY_INITIAL_CAPACITY = initialCapacity;
		capacity = initialCapacity;
		MY_LOAD_FACTOR = DEFAULT_LOAD_FACTOR;
		table = new Entry[capacity];
		size = 0;
	}

	public MyHashMap(int initialCapacity, float loadFactor) {
		if (initialCapacity < 0 || loadFactor <= 0.0) {
			throw new IllegalArgumentException();
		}

		MY_INITIAL_CAPACITY = initialCapacity;
		capacity = initialCapacity;
		MY_LOAD_FACTOR = loadFactor;
		table = new Entry[capacity];
		size = 0;
	}

	static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
		int hh = h;
        hh ^= (hh >>> 20) ^ (hh >>> 12);
        return hh ^ (hh >>> 7) ^ (hh >>> 4);
    }

    /**
     * Returns index for hash code h.
     */
    static int indexFor(final int h, final int length) {
        return h & (length - 1);
    }

	public void clear() {
		capacity = MY_INITIAL_CAPACITY;
		size = 0;
		table = new Entry[capacity];
	}

	public boolean containsKey(final K key) {
		if (key == null) {
			for (Entry se : table) {
				if (se != null) {
					if (se.getKey() == null) {
						return true;
					}
				}
			}
			return false;
		} else {
			for (Entry se : table) {
				if (se != null) {
					if (se.getKey() != null) {
						if (key.equals(se.getKey())) {
							return true;
						}
					}
				}
			}
			return false;
		}		
	}

	public boolean containsValue(final V value) {
		if (value == null) {
			for (Entry se : table) {
				if (se != null) {
					if (se.getValue() == null) {
						return true;
					}
				}
			}
			return false;
		} else {
			for (Entry se : table) {
				if (se != null) {
					if (se.getValue() != null) {
						if (value.equals(se.getValue())) {
							return true;
						}
					}
				}
			}
			return false;
		}
	}

	public V get(final K key) {
		if (key == null) {
            return getForNullKey();
		}

        int hash = hash(key.hashCode());
        for (Entry<K, V> se = table[indexFor(hash, table.length)];
        		se != null; se = se.getNext()) {
            K k;
            if (hash(se.getKey().hashCode()) == hash && ((k = se.getKey()) == key || key.equals(k))) {
                return se.getValue();
            }
        }
        return null;
	}

	private V getForNullKey(){
		for (Entry<K , V> se = table[indexFor(0, table.length)];
				se != null; se = se.getNext()) {
			if (se.getKey() == null) {
				return se.getValue();
			}
            if (hash(se.getKey().hashCode()) == 0) {
                return se.getValue();
            }
        }
        return null;
	}

	public boolean isEmpty() {
		return (size == 0);
	}

	public V put(final K key, final V value) {
		if (key == null) {
            return putForNullKey(value);
		}

        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K , V> se = table[i]; se != null; se = se.getNext()) {
            Object k;
            if (hash(se.getKey().hashCode()) == hash &&
            		((k = se.getKey()) == key || key.equals(k))) {
                V oldValue = se.getValue();
                se.setValue(value);
                return oldValue;
            }
        }

        addEntry(hash, key, value, i);
        return null;
	}

	private V putForNullKey(final V value) {
		int i = indexFor(0, table.length);
		for (Entry<K , V> se = table[i]; se != null; se = se.getNext()) {
			if (se.getKey() == null) {
				V res = se.getValue();
            	se.setValue(value);
                return res;
			}
            if (hash(se.getKey().hashCode()) == 0) {
            	V res = se.getValue();
            	se.setValue(value);
                return res;
            }
        }
		addEntry(hash(0), null, value, i);
        return null;
	}

	private void addEntry(final int hash, final K key, final V value, final int i) {
		if (table[i] == null) {
			table[i] = new SimpleEntry<K, V>();
		}
		if (table[i].getKey() == null && table[i].getValue() == null
				&& table[i].getNext() == null && table[i].getHash() == -1) {
			table[i] = new SimpleEntry<K, V>(key, value, hash);
		} else {
			Entry<K , V> se = table[i];
			while (se.getNext() != null) {
				se = se.getNext();
			}
			SimpleEntry<K, V> input = new SimpleEntry<K, V>(key, value, hash);
			se.setNext(input);
		}
		size++;

		if (size >= capacity * MY_LOAD_FACTOR) {
			Entry<K, V>[] temp = new Entry[2 * capacity];
			for (int j = 0; j < table.length; j++) {
				for (Entry<K , V> se = table[j]; se != null; se = se.getNext()) {
					int ii = indexFor(hash(se.getKey().hashCode()), temp.length);
					if (temp[ii] == null) {						
						temp[ii] = new SimpleEntry<K, V>(se.getKey(), se.getValue(),
								se.getHash(), null);
					} else {
						Entry<K , V> see = temp[ii];
						while (see.getNext() != null) {
							see = see.getNext();
						}
						see.setNext(new SimpleEntry<K, V>(se.getKey(), se.getValue(),
								se.getHash(), null));
					}
				}
			}
			table = temp;
			capacity = 2 * capacity;
		}
	}

	public V remove(final K key) {
		if (key == null) {
            return removeForNullKey();
		}

        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K , V> se = table[i]; se != null; se = se.getNext()) {
            Object k;
            if (hash(se.getKey().hashCode()) == hash
            		&& ((k = se.getKey()) == key || key.equals(k))) {
            	V res = se.getValue();
            	if (se.getNext() != null) {
            		Entry<K , V> see = table[i];
            		if (see != se) {
            			while (see.getNext() != se) {
            				see = see.getNext();
            			}
            			see.setNext(se.getNext());
            			se = null;
            		} else {
            			table[i] = new SimpleEntry<K, V>(se.getNext().getKey(),
            					se.getNext().getValue(), se.getNext().getHash(),
            					se.getNext().getNext());
            			se = null;
            		}
            	} else {
            		if (se != table[i]) {
            			Entry<K , V> see = table[i];
            			while (see.getNext() != se) {
            				see = see.getNext();
            			}
            			see.setNext(null);
            			se = null;
            		} else {
            			table[i] = null;
            		}
            	}
            	size--;
                return res;
            }
        }
        return null;
	}

	private V removeForNullKey() {
		int i = indexFor(0, table.length);
        for (Entry<K , V> se = table[i]; se != null; se = se.getNext()) {
            Object k;
            if (se.getKey() == null) {
            	V res = se.getValue();
            	table[i] = new SimpleEntry<K, V>();
            	table[i].setNext(se.getNext());
            	size--;
                return res;
            }
            if (hash(se.getKey().hashCode()) == 0) {
            	V res = se.getValue();
            	table[i] = new SimpleEntry<K, V>();
            	table[i].setNext(se.getNext());
            	size--;
                return res;
            }
        }
        return null;
	}

	public int size() {
		return size;
	}

	public Iterator<Entry<K, V>> entryIterator() {
		Iterator<Entry<K, V>> it = new Iterator<Entry<K, V>>() {

			private int i = 0;
						
            public boolean hasNext() {
            	return i < table.length;
            }

            public Entry<K, V> next() {
            	Entry<K, V> res = table[i];
            	i++;
                return res;
            }

            public void remove() {
                // TODO Auto-generated method stub
            }
        };
        return it;
	}

	public String toString() {
		String res = "";
		for (int i = 0; i < table.length; i++) {
			if (table[i] != null) {
				for (Entry<K , V> se = table[i];
						se != null; se = se.getNext()) {
					res += "Key: " + se.getKey()
							+ " | Value: " + se.getValue() + " | ";
				}
				res += "\n";
			} else {
				res += "Key: " + "-" + " | Value: " + "-" + "\n";
			}
		}

		return res;
	}
}
